// 2025/3/20
// https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked
// N皇后

class Solution {
    public:
        vector<vector<string>> ans;
        vector<string> tmp;
        string model;
    
        void setBoard(vector<vector<int>>& board, int i, int j, int k)
        {
            int n = board.size();
            for(int x = i + 1; x < n; x++)
            {
                int offset = x - i;
                board[x][j] += k;
                if(j - offset >= 0) board[x][j - offset] += k;
                if(j + offset < n) board[x][j + offset] += k;
            }
        }
    
        void dfs(vector<vector<int>>& board, int level)
        {
            if(level == board.size())
            {
                ans.push_back(tmp);
                return;
            }
    
            int n = board.size();
            for(int j = 0; j < n; j++)
            {
                if(board[level][j] == 0)
                {
                    model[j] = 'Q';
                    tmp.push_back(model);
                    model[j] = '.';
                    setBoard(board, level, j, 1);
                    dfs(board, level + 1);
                    setBoard(board, level, j, -1);
                    tmp.pop_back();
                }
            }
        }
    
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<int>> board(n, vector<int>(n, 0));
            model.clear();
            model.resize(n, '.');
            dfs(board, 0);
            return ans;
        }
    };